1. Field of the Invention
This invention relates to the field of three-dimensional imaging systems, and more particularly to a method and apparatus for creating three-dimensional models of objects from sets of arbitrary three-dimensional curves obtained from a target surface.
2. Description of Prior Art
Three-dimensional digitization and modeling systems are commonly used in many industries and their applications are numerous. A few examples of such applications are: inspection and measurement of shape conformity in industrial production systems, digitization of clay models for industrial design and styling applications, reverse engineering of existing parts, interactive visualization of objects in multimedia applications, and three-dimensional documentation of artwork and artifacts.
The shape of an object is digitized using a ranging sensor that measures the distance between the sensor and a set of points on the surface. From these measurements, three-dimensional coordinates of points on the target surface are obtained in the sensor reference frame. Prom a given point of view, the ranging sensor can only acquire distance measurements on the visible portion of the surface. To digitize the whole object, the sensor must therefore be moved to a plurality of viewpoints in order to acquire sets of range measurements that cover the entire surface. A model of the object is built by merging and registering the sets of range measurements in a common reference frame. Creating the three-dimensional model of an object is a multistep process usually comprising: (a) acquiring sets of range measurements from a plurality of viewpoints, (b) roughly aligning the sets of range measurements in a common reference frame, (c) refining the registration of the sets of range measurements in the common reference frame, (d) merging the range measurements in a unique non-redundant model, and (e) building a model of the surface using geometric primitives such as triangles.
Three types of ranging sensors are commonly used to digitize the surface of an object: (a) cloud of points sensors which provide unorganized sets of range measurements, (b) range image sensors which provide sets of measurements organized into regular matrices, and (c) curve sensors which provide range measurements organized into sets of three-dimensional curves, e.g. profiles. Cloud of points and range image sensors offer the advantage of providing a high density of measurements from a single viewpoint. They are however bulky and cumbersome to move from one viewpoint to the next. Due to their greater simplicity and robustness, curve sensors are usually favored for digitizing the entire shape of objects. These sensors can be easily moved from one viewpoint to the next, by either a mechanical system or simply an operator holding the sensor in hand.
Numerous examples of ranging sensor devices are described in the art. “Portable digital 3-d imaging system for remote sites” by J.-A. Beraldin et al., published in proceedings of the 1998 IEEE International Symposium on Circuit and Systems, Monterey, Calif., USA: 326-333. May 31-Jun. 3, 1998, describes a compact laser stripe range sensor that can be mounted, for instance on a translational or rotational stage. “A Self-Referenced Hand-Held Range Sensor” by P. Hebert, published in Proceedings of the IEEE International Conference on Recent Advances in 3-D Digital Imaging and Modeling, Quebec, pp. 5-12, May 2001, presents a hand-held range sensor gathering a set of curves issued from a crosshair laser projection pattern. In “A Review of 20 Years of Ranges Sensor Development” by F. Blais, published in, Videometrics VII, in Proceedings of SPIE-IS&T Electronic Imaging, SPIE Volume 5013 (2003), pp 62-76, NRC 44965, several range sensors are described, among these a range scanner collecting both 3-D measurements and color (R,G,B) properties is further described in “Digital 3-D Imaging, theory and applications” by M. Rioux, published in Proceedings of Videometrics III, SPIE vol. 2350, pp. 2-15, 1994.
Using curve sensors with current three-dimensional modeling systems requires that the sensor be moved in an organized and regular motion perpendicular to the direction of the measured profile. This, to simulate a range image that can be processed in the same way the output of a range image sensor would be. Since the range of motion is restricted to a single axis, the operation must be repeated multiple times to simulate the acquisition of range images from multiple viewpoints. In addition to imposing a regular unidirectional motion of the sensor, the main drawback with current systems that process data in this manner is that the alignment error of each curve cannot be individually corrected. As the set of curves acquired in a given motion sequence is processed as a rigid range image, only the global alignment error of the entire set of curves can be corrected by the modeling system, thus limiting the accuracy of the reconstructed surface.
No method has been developed in the art for creating a surface model from arbitrary three-dimensional curves. U.S. Pat. No. 5,946,645 issued Aug. 31, 1999 to Marc Rioux and Patrick Hebert describes a method for individually refining the alignment of arbitrary three-dimensional profiles. The method claimed relies on measuring the distance between each profile and every other profile in the set. Because of this combinatorial complexity, the method cannot currently be used in practice with the high number of curves typically needed to model an entire object. Furthermore, this patent does not describe any means for creating a model of the surface from the three-dimensional curves once their alignment has been refined. The use of this curve registration method on data acquired from a hand-held sensor is described in “Toward a hand-held laser range scanner: integrating observation-based motion compensation” by P. Hebert et al., published in Proceedings of SPIES, volume 3313, pages 2-13, January 1998.
A volumetric method for reconstructing surface models from unorganized clouds of three-dimensional points is described in “Surface Reconstruction from Unorganized Points” by H. Hoppe et al., published in SIGGRAPH '92 Proceedings, volume 26, pages 71-78, July 1992. The volumetric representation used by this method only contains the distance to the surface, which is sufficient to reconstruct the surface but does not contain enough information to refine alignment errors of data sets. This method is general and can be used to create a surface model for a set of arbitrary three-dimensional curves by converting it into an unorganized cloud of points. This process is difficult to implement in practice because it requires that the entire target surface be measured with a high and relatively uniform density. Doing so also eliminates the rigid arrangement of each curve in the set. This loss of information negatively impacts the quality and accuracy of the reconstructed surface because it becomes impossible to correct the alignment of curves. No method for refining the alignment of the three-dimensional data is described. A specialization of this surface reconstruction method for merging range images is described in “A Volumetric Method for Building Complex Models from Range Images” by B. Curless et al., published in SIGGRAPH '96, Proceedings, pages 303-312, 1996. This is a volumetric method that reconstructs the surface incrementally by adding range images to the model. The method exploits the structure of the images and cannot be used with arbitrary three-dimensional curves. As with the more general approach described by Hoppe, no method for refining the alignment of the three-dimensional data is described.
A method for reconstructing a surface from data acquired with a hand-held curve sensor is described in “Geometric Fusion for a Hand-Held 3D Sensor” by A. Hilton et al., published in Machine Vsion and Applications, 12:44-51, 2000. This method requires that the sensor is moved in a regular and organized motion in such a way to provide parallel curves that are merged into range images. Instead of directly using the three-dimensional curves to build the surface, this method must combine the curves into simulated range images. The main drawback of the method is that it poses severe constraints on the range of motion of the sensor. Also, since the curves are merged into images, the alignment error of each curve cannot be individually corrected.
“Registration and Integration of Multiple Range Images by Matching Signed Distance Fields for Object Shape Modeling” by T. Masuda published in Computer Vision and Image Understanding 87, pages 51-65, 2002 describes a volumetric method for surface reconstruction and alignment refinement based on signed distance fields. This method is however specific to range images and cannot be generalized to arbitrary three-dimensional curves because signed distance fields cannot be constructed from single curves.
There therefore exists a need for new methods for creating three-dimensional models of objects from sets of arbitrary three-dimensional entities obtained from a target surface and eliminating the need for moving the sensor in organized and regular motions to simulate the creation of range images.